//
//  ProblemOffer54.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/1.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 54. 二叉搜索树的第k大节点
 给定一棵二叉搜索树，请找出其中第k大的节点。
 
 示例 1:
 输入: root = [3,1,4,null,2], k = 1
    3
   / \
  1   4
   \
    2
 输出: 4
 示例 2:
 输入: root = [5,3,6,2,4,null,null,1], k = 3
        5
       / \
      3   6
     / \
    2   4
   /
  1
 输出: 4

 限制：1 ≤ k ≤ 二叉搜索树元素个数
 */
@objcMembers class ProblemOffer54: NSObject {
    func solution() {
        let root = TreeNode(3)
        root.left = TreeNode(1)
        root.left?.right = TreeNode(2)
        
        root.right = TreeNode(4)
        print(printNodeTree(root))
        print(kthLargestBFS(root, 1))
        
        let root1 = TreeNode(5)
        root1.left = TreeNode(3)
        root1.left?.left = TreeNode(2)
        root1.left?.left?.left = TreeNode(1)
        root1.left?.right = TreeNode(4)
        
        root1.right = TreeNode(6)
        print(printNodeTree(root1))
        print(kthLargestBFS(root1, 3))
    }
    
    /*
     将二叉搜索树：转换为中序遍历数组
     */
    func kthLargest(_ root: TreeNode?, _ k: Int) -> Int {
        let list:[Int] = kthLargestDFS(root)
        print(list)
        return list[list.count-k]
    }
    
    // 深度遍历：
    func kthLargestDFS(_ root: TreeNode?) -> [Int] {
        if root == nil {
            return []
        }
        var list:[Int] = []
        if root?.left != nil {
            list.append(contentsOf: kthLargestDFS(root?.left))
        }
        list.append(root!.val)
        if root?.right != nil {
            list.append(contentsOf: kthLargestDFS(root?.right))
        }
        return list
    }
    
    // 广度搜索
    func kthLargestBFS(_ root: TreeNode?, _ k: Int) -> Int {
        var list:[TreeNode] = [root!]
        // 1: 找到最右侧的页节点, 这是最大的值
        var node = root
        while node?.right != nil {
            node = node?.right
            list.append(node!)
        }
        // 遍历数
        var n = 0
        var lNode: TreeNode?
        while list.isEmpty == false {
            n += 1
            lNode = list.removeLast()
            if n == k {
                return lNode!.val
            }
            
            if lNode?.left != nil {
                lNode = lNode?.left
                list.append(lNode!)
                while lNode?.right != nil {
                    lNode = lNode?.right
                    list.append(lNode!)
                }
            }
        }
        return 0
    }
}
